class Solution {
public:
    vector<string> rst;
    vector<string> ipItem;
    vector<string> restoreIpAddresses(string s) {
        restoreIpAddressesItem(s, 0);
        return rst;
    }

    void restoreIpAddressesItem(string s, int start) {
        if(ipItem.size() == 3) {
            string lastItem = s.substr(start, s.size() - start);

            if(itemJudge(lastItem) == false) return;

            string ip = "";
            for(string item : ipItem){
                ip = ip + item + '.';
            }
            ip = ip + lastItem;

            rst.push_back(ip);
            return;
        }
        
        for(int i = start; i < s.length(); ++i) {
            string item = s.substr(start, i - start + 1);

            if(itemJudge(item) == false) return;
            
            ipItem.push_back(item);
            restoreIpAddressesItem(s, i + 1);
            ipItem.pop_back();
        }
    }

    bool itemJudge(string item) {
        // 空字符处理
        if(item.length() < 1) return false;

        // 前导 0 处理
        if(item.length() > 1 && item[0] == '0') return false;

        // 越界处理
        int sum = 0;
        for(char num : item){
            sum = sum * 10 + (num - '0');

            if(sum > 255) return false;
        }

        return true;
    } 
};